//
//  Problem821.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/20.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 921. 使括号有效的最少添加
 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

 它是一个空字符串，或者
 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
 它可以被写作 (A)，其中 A 是有效字符串。
 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

 示例 1：
     输入："())"
     输出：1
 示例 2：
     输入："((("
     输出：3
 示例 3：
     输入："()"
     输出：0
 示例 4：
    输入："()))(("
    输出：4

 提示：
     S.length <= 1000
     S 只包含 '(' 和 ')' 字符。
 */
@objcMembers class Problem821: NSObject {
    func solution() {
        print(minAddToMakeValidClear("())"))
        print(minAddToMakeValidClear("((("))
        print(minAddToMakeValidClear("()"))
        print(minAddToMakeValidClear("()))(("))
    }
    
    /*
     1: 创建一个堆栈，依次把s入栈
     2: 如果是"(", 直接入栈
     3: 如果是")", 如果栈顶是"("，把栈顶出栈, 如果数组是空的，入栈
     */
    func minAddToMakeValid(_ s: String) -> Int {
        var list:[Character] = []
        for c in s {
            if list.count == 0 || c == "(" {
                list.append(c)
            } else {
                if list.last! == "(" {
                    list.removeLast()
                } else {
                    list.append(c)
                }
            }
        }
        return list.count
    }
    
    /*
     节省空间
     1: 定义一个变量l：记录当前“(”的数量，定义一个遍历r：记录当前“)”的数量，
     2: 遍历字符串，如果遇到“(” l++, 遇到“)”，如果l==0，r++; l>0 l--
     */
    func minAddToMakeValidClear(_ s: String) -> Int {
        var l = 0, r = 0
        for c in s {
            if c == "(" {
                l += 1
            } else if l == 0 {
                r += 1
            } else {
                l -= 1
            }
        }
        return l + r
    }
}
